package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 插入区间
 */

public class Code057 {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {6, 9}};
        int[] newInterval = {2, 5};
        System.out.println(Arrays.deepToString(new Code057().insert(intervals, newInterval)));
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int maxEnd = 0;
        for (int[] interval : intervals) {
            maxEnd = Math.max(maxEnd, interval[1]);
        }
        maxEnd = Math.max(maxEnd, newInterval[1]);
        int[] diff = new int[2 * maxEnd + 2];
        for (int[] interval : intervals) {
            int start = interval[0], end = interval[1];
            diff[start * 2]++;
            diff[end * 2 + 1]--;
        }
        diff[newInterval[0] * 2]++;
        diff[newInterval[1] * 2 + 1]--;
        int[] interval = new int[diff.length];
        interval[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            interval[i] = interval[i - 1] + diff[i];
        }

        // 遍历前缀和数组，合并连续覆盖段
        List<int[]> result = new ArrayList<>();
        Integer start = null;

        for (int i = 0; i < interval.length; i++) {
            if (interval[i] > 0) {
                if (start == null) {
                    start = i;
                }
            } else {
                if (start != null) {
                    result.add(new int[]{start / 2, i / 2});
                    start = null;
                }
            }
        }

        // 转为二维数组返回
        return result.toArray(new int[0][]);
    }
}
